package com.example.leetcode.bfs;

import com.example.swing.MatrixVisualizer;
import javafx.util.Pair;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class leetcode733 {
    public static void main(String[] args) {
//        int[][] image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        int[][] image = {{0, 0, 0}, {0, 1, 0}};
        int sr = 0, sc = 0, color = 2;
        MatrixVisualizer.show(image);

        Solution solution = new Solution();
        int[][] flooded = solution.floodFill(image, sr, sc, color);
        System.out.println(Arrays.deepToString(flooded));
    }

    static class Solution {
        public int[] xDir = {-1, 1, 0, 0};
        public int[] yDir = {0, 0, -1, 1};

        public int[][] floodFill(int[][] image, int sr, int sc, int color) {
            boolean[][] visited = new boolean[image.length][image[0].length];
            int num = image[sr][sc];
            if (color == num) {
                return image;
            }

            return bfs(image, sr, sc, color, visited, num);
        }

        private int[][] bfs(int[][] image, int sr, int sc, int color, boolean[][] visited, int num) {
            Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
            queue.add(new Pair<>(sr, sc));
            visited[sr][sc] = true;
            image[sr][sc] = color;

            while (!queue.isEmpty()) {
                Pair<Integer, Integer> pair = queue.poll();
                int x = pair.getKey(), y = pair.getValue();
                for (int i = 0; i < 4; i++) {
                    int nx = x + xDir[i];
                    int ny = y + yDir[i];
                    if (!isValid(nx, ny, image) || visited[nx][ny] || image[nx][ny] != num) {
                        continue;
                    }
                    visited[nx][ny] = true;
                    image[nx][ny] = color;
                    queue.add(new Pair<>(nx, ny));
                }
            }
            return image;
        }

        public Boolean isValid(int x, int y, int[][] image) {
            int m = image.length;
            int n = image[0].length;
            return x >= 0 && x < m && y >= 0 && y < n;
        }
    }

//    static class Solution {
//        public int[] xDir = {-1, 1, 0, 0};
//        public int[] yDir = {0, 0, -1, 1};
//
//        public int[][] floodFill(int[][] image, int sr, int sc, int color) {
//            int num = image[sr][sc];
//            if (num != color) {
//                dfs(image, sr, sc, color, num);
//            }
//            return image;
//        }
//
//        public Boolean isValid(int x, int y, int[][] image) {
//            int m = image.length;
//            int n = image[0].length;
//            return x >= 0 && x < m && y >= 0 && y < n;
//        }
//
//        public void dfs(int[][] image, int row, int col, int color, int num) {
//            image[row][col] = color;
//            for (int i = 0; i < 4; i++) {
//                int newRow = row + xDir[i];
//                int newCol = col + yDir[i];
//                if (isValid(newRow, newCol, image) && image[newRow][newCol] == num) {
//                    dfs(image, newRow, newCol, color, num);
//                }
//            }
//        }
//    }
}
